package shuanfa;

import java.util.HashMap;
import java.util.Map;

//LRU算法 淘汰算法 淘汰最近最久未使用
public class LRU {
    public static void main(String[] args) {
        LRU lru = new LRU(2);
        lru.put(1,1);
        lru.put(2,2);
        System.out.println(lru.head.next.value);
        System.out.println(lru.get(1));
        System.out.println(lru.head.next.value);
    }
    Entry head,tail;
    int capacity;//链表容量
    int size;//链表中数据数
    Map<Integer,Entry> cache;
    public LRU(int capacity){
        this.capacity = capacity;
        //初始化链表
        initLinkedList();
        size = 0;
        cache = new HashMap<>(capacity + 2);
    }

    private void initLinkedList() {
        this.head = new Entry();
        this.tail = new Entry();
        head.next = tail;
        tail.pre = head;
    }

    /**
     * 将节点加入到头节点，如果节点已满，将会删除尾节点
     * @param key
     * @param value
     */
    public void put(int key,int value){
        Entry node = cache.get(key);
        if (node != null){
            node.value = value;
            moveToHead(node);//将该节点移动到头节点后一个节点
            return;
        }
        //不存在
        //如果容量已满 删除尾节点
        if (size == capacity){
            Entry lastNode = tail.pre;
            deleteNode(lastNode);
            cache.remove(lastNode.key);//删除缓存
            size--;
        }
        //加入新节点 加到头节点位置
        Entry newNode = new Entry(key, value);
        addNode(newNode);
        cache.put(newNode.key,newNode);
        size++;
    }

    public int get(int key){
        Entry node = cache.get(key);
        if (node == null){
            return -1;
        }
        //存在 移动节点
        moveToHead(node);
        return node.value;
    }
    private void addNode(Entry node) {
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }

    private void deleteNode(Entry node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
    }

    private void moveToHead(Entry node) {
        deleteNode(node);
        addNode(node);
    }

    public static class Entry{
        public Entry pre;
        public Entry next;
        public int key;
        public int value;

        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public Entry() {
        }
    }

}
